package com.lzp.leetcode

/**
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 * @describe:验证二叉搜索树
 * @Author: lixiaopeng
 * @Date: 4/15/21
 *
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
 */

fun main() {
    val node = TreeNode(10)
    node.left = TreeNode(9)
    node.right = TreeNode(11)
    println("合适的结果：${solution(node)}")

    val node1 = TreeNode(10)
    node1.left = TreeNode(13)
    node1.right = TreeNode(11)
    println("不合适的结果：${solution(node1)}")
}

/**
 * 递归法
 */
fun solution(node: TreeNode?): Boolean {
    if (node == null) return true
    //验证左
    if (node.value < node.left?.value ?: Int.MIN_VALUE) {
        return false
    }

    if (node.value > node.right?.value ?: Int.MAX_VALUE) {
        return false
    }

    return solution(node.left) && solution(node.right)
}

data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null) {

}
